1. Field of the Invention
Apparatuses and methods consistent with the present invention relate to a Viterbi decoder and a decoding method, and more particularly, to a Viterbi decoder executing a trace-back work in parallel using a plurality of memories connected to one another in parallel so as to improve a decoding speed and a decoding method.
2. Description of the Related Art
With the development of communication technology, wireless mobile communication technology has been popularized all over the world. Data is transmitted and/or received wirelessly in such a wireless mobile communication environment. Thus, data may be distorted by an effect such as noise during a transmission of the data. In general, to reduce the possibility of such a distortion, the transmitter codes and transmits data to be transmitted, and the receiver decodes the data. Also, coding and decoding works are executed during storing of data from a recording medium such as a digital versatile disc (DVD).
Such a coding method may be of various types such as a block coding method, a convolution coding method, and the like. In the block coding method, additional data with a predetermined bit size is added to an input data bit and then coded. In the convolution coding method, previously input data is stored in a memory to perform coding based on a correlation between a current input value and a previous input value. Compared to the block coding method, the convolution coding method has high error correction efficiency and thus is generally used.
A Viterbi decoder decodes data coded using the convolutional coding method. The Viterbi decoder performs a multi-step operation, accumulates the result of the multi-step operation, and determines an optimum path from the accumulated result values so as to correct an error.
FIG. 1 is a schematic view of a trellis diagram used in a general Viterbi decoder. In the trellis diagram shown in FIG. 1, a constraint length K is “3,” and a coding rate is “½.” The trellis diagram includes a plurality of processing nodes corresponding to lapses of time, and a processing node 10 of the plurality of processing nodes includes a plurality of states 11 through 14.
Since the constraint length K is “3,” the trellis diagram includes 23−1=4 states. Each of the states is assigned previously input bit values, i.e., bit values such as “00,” “10,” “01,” and “11.” The Viterbi decoder calculates a path metric using a distance between an inherent code assigned to each branch on the trellis diagram and a substantially input signal as a branch metric. The path metric is stored in a memory. Thus, if a final path metric is stored, a trace-back work is executed. In other words, a minimum value of the final path metric is selected so that a trace-back work is performed starting from a first state in which the minimum value is recorded. A path metric of a state of states of a previous processing node connected to the first state is checked. Thus, a path in which the checked path metric is minimum is selected as an optimum path. As a result, if the selected optimum path has passed branches marked with solid lines, the selected optimum path is decoded as “0.” If the selected optimum path has passed branches marked with dotted lines, the selected optimum path is decoded as “1.”
A trace-back of decoding steps of the Viterbi decoder greatly affects power consumption and decoding time. A conventional Viterbi decoder executes such a trace-back process using various methods.
In a first type of trace-back work, the trace-back work is executed whenever each of the bits is decoded. In other words, if a trace-back memory includes 64 trace-back memory cells and 64 input values are input to calculate path metrics, the trace-back work is executed stating from the 64th memory cell. Thus, the first input value is decoded. Since the memory cells of the track-back memory have circulating structures, a path metric corresponding to a next input value is recorded in a decoded memory cell. Thereafter, the track-back work is executed stating from the first memory cell to decode the second input value. As a result, the 64 input values are sequentially decoded stating from the first input value. However, according to this method, since the trace-back work is executed with respect to each of the bits, a large amount of power is consumed.
In a second type of trace-back work, a capacitance of a trace-back memory may be increased. In this case, information as to state transition values obtained from a previous trace-back step is stored in the trace-back memory. Thus, if a point of time when an optimum path traced back in a current step coincides with an optimum path traced back in a previous step, the trace-back work in the current step stops and decoding may be executed using the optimum path traced back in the previous step.
In other words, if the trace-back work is executed up to a predetermined length or more, a point converging into a path through which a previous track-back work has been executed is detected. In this case, the trace-back work is not executed starting from the converging point but decoding may be immediately performed. Thus, although a value of an input signal received prior to the converging point is not traced back, the value may be decoded at a time. As a result, a number of times trace-back work is performed may be reduced, which reduces power consumption. However, according to this method, after decoding is performed one time, a time delay occurs until decoding is performed the next time. Therefore, this method may not be used in the fields requiring high speed decoding.